package 寒假刷题;

import java.util.ArrayList;
import java.util.List;

public class 和为K的最少斐波那契数字数目 {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int a = 1,b = 1;
        //记录所有小于等于 k 的斐波那契数
        while (a+b<=k){
          int c = a+b;
          list.add(c);
          a = b;
          b = c;
        }
        int ans = 0;
        //每次尽可能取最大的斐波那契数
        for (int i = list.size()-1; i >=0 && k>0 ; i--) {
            Integer num = list.get(i);
            if (k>=num){
                k-=num;
                ans++;
            }
        }
        return ans;
    }
}
